1. Field of the Invention
This invention relates generally to memory circuits, and more specifically to systems and methods for improved content addressable memory searching using selectable memory blocks.
2. Description of the Related Art
A content addressable memory (CAM) semiconductor device is a device that allows the entire contents of the memory to be searched and matched instead of having to specify one or more particular memory locations in order to retrieve data from the memory. Thus, a CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks.
CAMs provide performance advantages over conventional memory devices having conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired search term, or comparand, against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a non-CAM based database of 1000 entries may take ten separate search operations whereas a CAM device with 1000 entries may be searched in a single operation, resulting in significant time and processing savings. Internet routers often include a CAM for searching the address of specified data, allowing the routers to perform fast address searches to facilitate more efficient communication between computer systems over computer networks.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically contains an address, pointer, or bit pattern entry. In this configuration, a CAM may perform xe2x80x9creadxe2x80x9d and xe2x80x9cwritexe2x80x9d operations at specific addresses as is done in conventional random access memories (RAMs). However, unlike RAMs, data xe2x80x9csearchxe2x80x9d operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of pre-stored entries (i.e., rows) can be performed.
FIG. 1 shows a simplified block diagram of a conventional CAM 100. The CAM 100 includes a data bus 102 for communicating data, an instruction bus 104 for transmitting instructions associated with an operation to be performed, and an output bus 106 for outputting a result of the operation. For example, in a search operation, the CAM 100 may output a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data.
In operation, the CAM 100 uses search data, or xe2x80x9ccomparandxe2x80x9d, supplied using the data bus 102, to perform a parallel compare of the comparand to all of the valid entries stored within the CAM 100. If a match is found, referred to as a xe2x80x9chitxe2x80x9d, the address of the matching entry is output from the CAM using the output bus 106. In cases where multiple entries match the comparand, such as when a xe2x80x9cternaryxe2x80x9d CAM is used that allows entries to include bits with a xe2x80x9cdon""t carexe2x80x9d state, the CAM 100 may have a priority encoder that resolves the address of the highest priority matching entry.
The CAM often performs look-up functions based on elements of a cell, frame, packet, or datagram header to make intelligent forwarding decisions. The process is similar to a post office reading the address on an envelope to determine the next post office to which the envelope will be delivered. To satisfy the constant need for increasing bandwidth and table size, CAMs have become increasingly fast and dense. Frequently, CAMs are pipelined to increase the look-up rate of the CAM, allowing several look-up functions to be executed in parallel.
While CAMs offer one of the fastest look-up solutions currently available, they have the potential to consume significant power as CAMs scale for increasing density and speed. The parallel search associated with each search operation requires that the comparand be compared to every valid entry in the table. This causes significant consumption of power as many long internal metal tracks transition from one power rail to the other. This type of power is frequently referred to as xe2x80x9cCV2Fxe2x80x9d power since it is derived from the capacitance of the nodes that are transitioning, the square of the voltage difference between the beginning and the end of the transition and the frequency of the transition.
Although most of the CAM memory includes valid entries, often many sections of memory having valid entries do not include actual address data and thus will present a xe2x80x9cmissxe2x80x9d when the search data is compared to these entries. Since, power consumed in determining an entry does not match the comparand is effectively wasted, searching these entries waste power.
In view of the foregoing, there is a need for low power search methods for use in content addressable memory circuits. The methods should reduce the power required to perform searches in the CAM and preferably not waste power searching entries known to contain non-usable data.
Broadly speaking, the present invention fills these needs by providing architectures and methods that significantly reduce the power consumption of a CAM by using a block select method applied coincident with search input data. In one embodiment, a CAM is disclosed having a plurality of memory blocks for storing data within the CAM, and a search port in communication with the plurality of memory blocks. The search port is capable of facilitating search operations using the memory blocks. Also included in the CAM is a block select bus capable of selecting at least one specific memory block from the plurality of memory blocks. By using the block select bus, the search operations are performed using only the selected memory blocks. A maintenance port can also be included that is in communication with the plurality of memory blocks. The maintenance port is capable of facilitating maintenance operations using the memory blocks. Similar to search operations, the block select signal or a similar signal is capable of selecting at least one specific memory block from the plurality of memory blocks, wherein the maintenance operations are performed using only the selected memory blocks.
In another embodiment, a system is disclosed for selecting memory blocks within a content addressable memory. The system includes a block select memory that stores a plurality of memory block selection configurations. Each of the memory block selection configuration determines specific memory blocks of a CAM to enable for a CAM operation. Also included is a binary decode circuit for decoding a binary block select signal. The binary decode circuit selects a particular block selection configuration to utilize for a CAM operation. In one aspect of the present invention, the block select memory includes a block select configuration register having a plurality of bytes, with each byte storing a memory block selection configuration. Each byte comprises a plurality of bits, with each bit in communication with a particular memory block of the CAM. Each bit is then used to enable and disable the particular memory block in communication with the bit. In another aspect, the block select memory includes a plurality of block selection registers, where each block selection register stores a memory block selection configuration. Each block selection register includes a plurality of bits, with each bit in communication with a particular memory block of the CAM and capable of enabling and disabling the particular memory block in communication with the bit.
A system for low power operation of a CAM is disclosed in a further embodiment of the present invention. The system includes a CAM having a plurality of memory blocks, and a block select bus in communication with the CAM, where the block select bus is capable of selecting particular memory blocks from the plurality of memory blocks. The system also includes a first functional circuit capable of outputting a binary block select pattern to the block select bus by applying a first function to received search data. The binary block select pattern determines particular memory blocks to utilize for a search operation. In addition, a second functional circuit capable of outputting a binary block select pattern by applying the same first function to received maintenance data can be included. The binary block select pattern determines particular memory blocks to utilize for a maintenance operation.
In yet a further embodiment, a CAM having multiple tables for data storage is disclosed. The CAM includes a plurality of memory blocks that are partitioned into groups of memory blocks, with each group of memory blocks representing a table. A block select memory is also included that stores a plurality of table selections, wherein each table selection determines a particular group of memory blocks to use in a CAM operation. As above, the block select memory can include a block select configuration register having a plurality of bytes, with each byte storing a table selection. Optionally, the block select memory can include a plurality of block selection registers, with each block selection register storing a table selection.
Advantageously, the embodiments of the present invention reduce power consumption by searching only the CAM arrays capable of providing a chance of a xe2x80x9chitxe2x80x9d. Moreover, using the block select configuration register of the embodiments of the present invention, increased flexibility is achieved via software programmability. Specifically, the block select configuration register can be programmed online using software since there is no hard binding between a particular block select signal pattern and which particular CAM arrays get selected based on that pattern.
Thus, for example, if only a quarter of a CAM is currently being used, then only that quarter could be searched. However, if two years later the entire CAM is needed, the CAM can be reprogrammed online to search the entire CAM. Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.